package com.wfs.suanfa.leet;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class LRUCache<K,V> {

    static class Entry<K,V>{
        public Entry<K, V> prev;
        public Entry<K, V> next;
        public K key;
        public V val;
        public Entry() {}
        public Entry(K key, V val) { this.key = key; this.val = val; }
    }

    private Entry<K, V> head, tail; // 虚拟头节点和虚拟尾节点
    private final int capacity;     // 缓存容量
    private int size;               // 缓存占用量
    Map<K, Entry<K, V>> cache;      // 哈希表，记录双向列表节点的地址值

    public LRUCache(int capacity) {
        this.capacity = capacity;
        initCache();
    }
    // 初始化LRU缓存
    private void initCache() {
        head = new Entry<>();
        tail = new Entry<>();
        head.next = tail;
        tail.prev = head;
        size = 0;
        cache = new HashMap<>(this.capacity);
    }
    private V get(K key) {
        Entry<K, V> entry = cache.get(key);
        if(entry != null) {
            moveToTail(entry);
            return entry.val;
        } else {
            return null;
        }
    }

    private void moveToTail(Entry<K, V> entry) {
        deleteEntry(entry);
        addToTail(entry);
    }



    private void deleteEntry(Entry<K, V> entry) {
        if (Objects.isNull(entry)){
            return;
        }
        entry.prev.next=entry.next;
        entry.next.prev=entry.prev;
    }
    private void addToTail(Entry<K, V> entry) {
        if (Objects.isNull(entry)){
            return;
        }
        entry.next=tail;
        entry.prev=tail.prev;
        tail.prev.next=entry;
        tail.prev=entry;
    }
    private void put(K key,V val){
        Entry<K, V> entry = cache.get(key);
        if(entry != null) {
            // 缓存命中
            entry.val = val;
            moveToTail(entry);
        } else {
            // 缓存未命中
            if(size == capacity) {
                // 缓存已满，删除链表头部节点
                Entry<K, V> h = head.next;
                deleteEntry(h);
                cache.remove(h.key);
                size--;
            }
            // 添加新页面到链表尾部
            Entry<K, V> newEntry = new Entry<>(key, val);
            addToTail(newEntry);
            cache.put(key, newEntry);
            size++;
        }
    }
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(2);
        cache.put(1,"可口可乐");
        cache.put(2,"雪碧");
        System.out.println("页面1的内容：" + cache.get(1));
        cache.put(3,"果粒橙"); // 此时缓存已满，且页面2最久未被使用（因为cache.get(1)访问了页面1），页面2被置换成页面3
        System.out.println("页面2的内容：" + cache.get(2)); // 页面2已被换出，访问不到
    }

}
